package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1291 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码，自己只理解思想
     * 经典解法，每日一看
     * 典型的矩形前缀和+二分查找
     * @return:
     */
    class Solution {
        int m, n;

        public int maxSideLength(int[][] mat, int threshold) {
            m = mat.length;
            n = mat[0].length;
            int[][] sums = new int[m + 1][n + 1];
            //基本矩形前缀和，有看不懂的小伙伴先去学习矩形前缀和
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + mat[i - 1][j - 1];
                }
            }
            //二分查找满足要求的正方形最大边长, 最大为m,n的最小值
            int l = 0, r = Math.min(m, n);
            while (l < r) {
                int mid = l + (r - l + 1 >> 1);
                if (getMin(sums, mid) > threshold) {
                    r = mid - 1;
                } else {
                    l = mid;
                }
            }
            return l;

        }

        //求边长为k的正方形最小值
        private int getMin(int[][] sums, int k) {
            int min = Integer.MAX_VALUE;
            for (int i = k; i <= m; i++) {
                for (int j = k; j <= n; j++) {
                    int val = sums[i][j] - (sums[i - k][j] + sums[i][j - k] - sums[i - k][j - k]);
                    min = Math.min(min, val);
                }
            }
            return min;
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC1291 an = new LC1291();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
